QLISP.MSG[P,LES] - www.SailDart.org

perm filename QLISP.MSG[P,LES] blob sn#851477 filedate 1988-01-07 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00023 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 APPENDIX D -- Budget for three years beginning 1 June 1985.
C00007 00003 Capital equipment
C00009 00004 Lucid
C00013 00005 Qlisp first task
C00016 00006 ---------------------------------------------------------------------------
C00020 00007 Introduction
C00032 00008 Tools for parallel symbolic programming
C00036 00009 Facilities and Support
C00040 00010 Collaboration and connections with other projects
C00043 00011 Parallel Algorithms for Algebraic Manipulation
C00051 00012 APPENDIX A
C00073 00013 APPENDIX D -- Budget for eighteen months beginning 1 December 1985.
C00078 00014 U.C. Berkeley Budget
C00090 00015 Lucid
C00094 00016 APPENDIX D -- Budget for eighteen months beginning 1 December 1985.
C00098 00017 Capital equipment
C00100 00018 Lucid
C00103 00019 Qlisp revised budget
C00108 00020 Qlisp Task Description
C00119 00021 Qlisp Task
C00131 00022 BUDGET (18 months)
C00136 00023 Lucid
C00141 ENDMK
C⊗;
APPENDIX D -- Budget for three years beginning 1 June 1985.

Stanford University proposal to DARPA
for
Qlisp on parallel processors

Budget for year 1 2 3
beginning 6-1-85 6-1-86 6-1-87
Personnel
Prof. John McCarthy, Principal Investigator 19,713 19,713 19,713
(15% acad. yr., 50% summer)

Lester Earnest, Senior Res. Assoc. (100%) 67,500 67,500 67,500

Carolyn Talcott*, Research Associate (100%) 43,000 43,000 43,000

-----, Research Associate (100%) 41,000 41,000 41,000

-----, Computer Systems Analyst (100%) 40,000 40,000 40,000

-----, Computer Technician (25%) 8,000 8,000 8,000

Ross Casley, Student Research Assistant 12,600 12,600 12,600
(50% acad. yr., 100% summer)
Ian Mason, Student Research Assistant 12,600 12,600 12,600
(50% acad. yr., 100% summer)
-----, Student Research Assistant 12,600 12,600
(50% acad. yr., 100% summer)
-----, Student Research Assistant 12,600 12,600
(50% acad. yr., 100% summer)
-----, Secretary (50% time) 10,440 10,440 10,440
------- ------- -------
Salary subtotals 254,853 280,053 280,053

Allowance for salary increases (9%/yr) 0 25,205 52,678
------- ------- -------
Salary totals 254,853 305,258 332,731

Staff benefits (24.1% initially, 63,892 77,993 86,676
25.4% beg. 9/1/85, 25.6% beg. 9/1/86,
26.2% beg. 9/1/87)
Consultants (10 days/yr. @ $500) 5,000 5,000 5,000

Travel (8 East Coast trips/yr. @ $1000, 15,000 15,300 16,300
14 Western trips @ $500, adjusted for
inflation)
Computer maintenance 73,819 73,819 73,819
(based on Sequent Computer)
Computer time costs (based on 1984 usage 36,000 48,000 48,000
of SAIL computer usage by principals)
Other direct costs 22,600 26,900 28,600
------- ------- -------
Subtotal 471,164 552,270 591,126

* To be appointed.
Capital equipment
2 multiprocessor computer systems
(e.g. Sequent Balance 8000 systems) 615,160
Ethernet workstation cluster (8 term.) 24,000
Ethernet page printer 11,937
Additional workstations & peripherals 12,000 8,000

Lucid subcontract 518,000 408,300 234,600

U.C. Berkeley subcontract 182,000 215,300 226,700

Indirect costs (69% of direct costs, 359,603 381,066 407,877
excluding all capital equipment and
subcontract amounts over $25,000) ------- ------- -------

Total by year 2,181,864 1,568,936 1,468,303
------- ------- -------
Project cumulative total 2,181,864 3,750,800 5,219,103

Lucid
Project Cost Estimate
($000's)

Year 1 Year 2 Year 3 Total

Direct Labor (Sch. A) 109.2 113.4 62.3 284.9

Salary Related Expense @19.8% 21.6 22.5 12.3 56.4
------------------------------------
Salary Expense 130.8 135.9 74.6 341.3

Overhead @148% 193.6 201.1 110.4 505.1

Other Direct Project Costs
(Sch. B) 126.0 18.0 19.0 163.0
------------------------------------
450.4 355.0 204.0 1009.4

Fee @15% 67.6 53.3 30.6 151.5
------------------------------------
Total Project Cost 518.0 408.3 234.6 1160.9

Notes:
1. Project cost assumes 1 Sequent machine provided to Lucid at no additional
cost located at Lucid facilities for duration of project.

2. Salary Related Expense and overhead are provisional rates based on FY86
(year end June 30) business plan projections.

3. Direct Labor rates escalated at 10% per year.

Schedule A
Direct Labor
($000's)

Year 1 Year 2 Year 3

Principal Investigator
man-months 3 2 1
rate per month 6.0 6.6 7.3
total dollars 18.0 13.2 7.3

Senior Scientist
man-months 12 12 12
rate per month 5.0 5.5 6.1
total dollars 60.0 66.0 36.1

Scientist
man-months 6 6 3
rate per month 4.2 4.6 5.1
total dollars 25.2 27.6 15.3

Technician
man-months 2 2 1
rate per month 3.0 3.3 3.6
total dollars 6.0 6.6 3.6

Total Man-Months 23 22 10

Total Dollars 109.2 113.4 62.3

Schedule B
Other Direct Project Costs
($000's)

Year 1 Year 2 Year 3 Total

Computer Equipment & Supplies
Symbolics 3670 108
Supplies @ 3K/yr 3 3 3 9
Stanford Communication 2 1 1 4

Travel & Subsistence
Air
2 trips to Washington, D.C. @1.5 ea.
1 trip to National Conference @1.5
4 trips to East Coast, technical workshop @1.5 ea.

Local travel @.5/yr 11 12 13 36
escalate @10%/yr

Printing and Reproduction @2K/yr 2 2 2 6
------------------------------------
Total 126 18 19 163

Qlisp first task
Steve and John:

Here is a slightly revised version of the Qlisp proposal, with the initial
implementation effort broken out as a task to be performed over an 18
month period. As we discussed, this task could be assigned to the
existing contract (N00039-84-C-0211) for advanced R&D in computer science.
The proposed period of performance (12/1/85 through 5/31/87) is chosen to
begin as early as seems practical and to extend to the current termination
date of the cited contract.

As revised, this proposal presents the whole work plan but requests
funding just for the initial implementation phase. Funding to support
applications testing and tuning tasks is to be requested subsequently.
Relative to the earlier submission, we have figured out a way to save
some capital equipment money: instead of getting one machine for Stanford
and one for Lucid, we plan to install a microwave link between Lucid's
new quarters (they will move shortly) and the Stanford ethernet environment,
which is in turn tied to ARPAnet. We expect that this will provide adequate
computational support for the three main parties to this proposal for at
least the period of this task.

We stand ready to crank this through the Stanford mill at the earliest sign
of encouragement. Please let me know if you see any problems.

Best Regards,
Les Earnest

---------------------------------------------------------------------------

STANFORD UNIVERSITY

Proposal to

Defense Advanced Research Projects Agency

Qlisp for Parallel Processors

John McCarthy, Professor of Computer Science
Principal Investigator

Task Summary

An extension of Common Lisp for parallel processing, called Qlisp, is
planned to use queue-based multi-processing. It has the following
features.

o Each processor can address the whole of memory, and a processor may
execute programs anywhere in memory on data located anywhere in memory.

o The programmer indicates when parallelism is possible by using parallel
constructions in the source language, which is an extension of Lisp.

o When a program comes to a statement allowing parallelism and decides
(according to the computed value of an allow-parallelism parameter
in the statement) that parallelism is to be invoked, it adds a
collection of tasks to a queue and starts on the first.

o When a processor completes a task it goes to the queue for its next task.

Basing parallelism on run-time queues means that a program isn't written
or compiled for any specific number of processors. The number available
can even change during the course of a computation. Tasks need not be of
similar length, because a processor finishing a short task merely takes
another from the queue.

This project will involve a collaboration between Stanford University,
University of California at Berkeley and Lucid, Inc. An initial task of
18 months duration will produce a functioning Qlisp system, documentation
and debugging tools at a cost of $2.6 million.

This is proposed as a step toward the longer range goal of demonstrating
symbolic computation in a parallel computing system. The follow-on task,
to be proposed for funding later, will apply, evaluate, and tune the Qlisp
system on demonstration tasks in symbolic computation. For comprehensibility,
this proposal describes both tasks.

Introduction

This is a proposal for research in implementing and demonstrating
applications of an extension of Lisp for parallel processing called Qlisp.
The scheme under discussion was called ``Qlambda'' in Gabriel and
McCarthy (1984). An extension of that paper is included as Appendix B.
The name ``Qlambda'' was used instead of ``Qlisp'' because there had been
an earlier system called Qlisp developed by Earl Sacerdoti. In a recent
discussion, Dr. Sacerdoti indicated that the earlier Qlisp has been out of
use long enough that he thinks the likelihood of confusion arising from
reuse of the name is small. Therefore we are adopting the preferred name
of ``Qlisp.''

Qlisp allows the programmer to specify tasks that may be performed in
parallel by creating queues of tasks. The project involves acquiring a
parallel processor, developing Qlisp for it, developing test applications
for it (algorithms for algebraic mathematics comparable to those of
Macsyma), and testing the performance of the applications on substantial
symbolic computation tasks.

The project will be carried out with both formal and informal
collaboration among several groups. The principal investigator for the
overall project will be Professor John McCarthy. The Qlisp implementation
will be done under subcontract to Lucid Inc. The design and
implementation of Qlisp will be supervised by Richard P. Gabriel of Lucid.
The Macsyma application will be developed in collaboration with Professor
Richard Fateman of the University of California at Berkeley. Separate
proposals for the Lucid subcontract and Fateman's contribution to the
Macsyma application are attached. Development of parallel programming
tools and programs for testing applications will be supervised by Carolyn
Talcott. We expect to interact substantially with other symbolic parallel
processing projects at Stanford and Berkeley. This interaction is
outlined below. The parallel facility and Qlisp will be available on the
ARPAnet for others to try out.

It is generally agreed that the main hope for large increases in computer
speed, whether for numerical work or symbolic computation as in artificial
intelligence, lies in massive parallelism. Projects are being undertaken
that will involve hundreds or even thousands of processors. However,
no one has yet demonstrated the ability to make general purpose use of
even two processors on symbolic computation for a single problem. Indeed
even numerical computation on parallel processors has been difficult, and
there are no general purpose computation systems that make good use of
parallel processors in spite of more than twenty years of work.
Therefore, it is important to explore a variety of approaches to getting
good performance from parallel processors on a variety of problems.

Our approach is queue-based multi-processing. It has the following
features.

1. Each processor can address the whole of memory, and a processor
may execute programs anywhere in memory on data located anywhere in memory.
This makes difficulty for the hardware designer, but we are running scared
on programming, and we cannot necessarily accept the forms of parallelism
that hardware people find most convenient to implement.

2. The programmer indicates when parallelism is possible by using
parallel constructions in the source language, which is an extension of
Lisp. See Gabriel and McCarthy 1984, an extension of which is included as
Appendix B, for a description of this language called Qlisp.

3. When a program comes to a statement allowing parallelism and decides
(according to the computed value of an allow-parallelism parameter in the
statement) that parallelism is to be invoked, it adds a collection of
tasks to a queue and starts on the first. When a processor completes a
task it goes to the queue for its next task. It may execute some queue
management code to decide what to do next.

4. Basing parallelism on run-time queues means that a program isn't
written or compiled for any specific number of processors. The number
available can even change during the course of a computation. Tasks need
not be of similar length, because a processor finishing a short task merely
takes another from the queue.

5. While Qlisp is more fully described in the paper, we mention
just the statement QLET here. Its form is

QLET allow ((x1 arg1))
. . .
. . .
. . .
((xn argn)).body).

The parameter "allow" is evaluated first. If its value is (), i.e. false,
parallelism is not allowed and the QLET statement behaves like an ordinary
Common Lisp LET. If the value is something else and not EAGER, then a
queue of tasks is set up to evaluate arg1 ... argn, and the processor
takes a task from the queue. If the value is EAGER, the processor sets up
the queue and immediately starts on evaluating body, suspending if it
comes to a variable whose value has not yet been computed.

The point of exhibiting QLET here is that the parameter allow is evaluated
to determine whether parallelism is allowed. Because Lisp (and symbolic
computation generally) is highly recursive, it can generate a large number
of parallel tasks. However, we need only enough parallelism to keep our
processors busy. Therefore, the expression allow should often be false.
Qlisp is designed according to the idea that it is necessary to limit
parallelism as well as to instigate it.

We believe that it is necessary to follow through on the
development and implementation of Qlisp by trying it out on
substantial applications. These trials will most likely lead to
improvements in Qlisp and in the parallel processing hardware.
They may also determine whether it is possible to relax the requirement
that all memory be equally accessible to all processors, since
the hardware people find this expensive to implement.

There are two kinds of problems that to which parallelism
can be applied. In one case the goal is make what you already have run
faster. This improves interaction with the computer and allows larger
problems to be addressed. In the second case, speed is of the essence.
Part of of the algorithm is devoted to insuring speed and some sort of
``real time'' behavior. For example, a process may want to time out or
use some default value if a subprocess does not reply within a given time
limit. Qlisp primitives directly address problems of the first sort.
Additional primitives may be needed for the real-time applications. For
this a number of questions will need to be answered. Can the additional
primitives can be coded in Qlisp? Can they be coded easily and
efficiently?

We have chosen a Macsyma-like system as an initial target application. This is an application of the first sort.
Our reasons for choosing this rather than an AI application are the following.

1. Macsyma and similar systems like REDUCE and SMP use a wide variety
of algorithms each with its own inner loop and each of which presents its
own problems of parallelism.

2. When a sufficient number of features have been implemented,
we can compare performance with algebraic computation systems running
on single processors.

3. The task is definite enough to be readily defined and supervised.
Some of our group are eager to undertake it.

We are also thinking about possible AI applications, e.g. to problem solving,
but are not ready to decide on one.

Tools for parallel symbolic programming

The work proposed here involves an entirely new style of programming and
will require the development of new methods and tools to support the
programming activity. This development will be carried out in parallel
with and in support of the chosen application.

Algorithm design

Part of the development of parallel lisp involves discovering what
primitives are needed to carry out various tasks. This involves
classifying problems as to the sort of parallelism required and the design
of control structures appropriate for the various classifications. Two
well known classifications are AND versus OR parallelism and asynchronous
tasks with occasional interactions versus synchronous tasks operating on a
shared data structure. Somewhat newer ideas include pipelines and other
geometric structures that make it easy to visualize the interactions among
a set of processes. These latter ideas are discussed in
Appendix B. In some cases successful use of parallelism will
require design of data structures with information making them suited to
parallel processing.

Methods for debugging.

Traditional Lisp debugging methods such as stepping and tracing are not
going to be adequate for debugging Qlisp programs. Programmers will
need to learn where to look for bugs and to devise methods for identifying
meaningful checkpoints. We will build tools for for monitoring the
progress of a set of processes working on a problem. We will also work on
informal methods of specification and reasoning about Qlisp programs as
aids to the process of program development and testing.

Benchmarks and measures of success.

We will design benchmarks for testing parallel lisps and for comparing
the relative efficiency of parallel and sequential algorithms. We will
also develop tools for measuring factors such as degree of parallelism
achieved, queue management overhead, and memory contention. Some
measuring tools have already been developed by Gabriel in a sophisticated
system for simulating execution of Qlisp programs. This system was used
in initial experiments testing Qlisp primitives.

Facilities and Support

In order to develop and test the scheme outlined above, it will be
necessary to have access to machines that execute multiple instruction
streams concurrently. There are a number of novel machines with parallel
architectures in various stages of development currently and it is not
clear which approaches will emerge as the most cost/effective in the long
run.

In view of this, we propose to acquire a system that is commercially
available and relatively mature, both in hardware and in operating system,
so that our parallel software development efforts can proceed with
relatively little impairment from developmental bugs in the basic hardware
and operating system. It will not be necessary to acquire a functionaly
complete computer system, including all necessary peripherals---existing
computer facilities at Stanford, including SAIL and SCORE computers, can
provide some of these functions.

We propose that a substantial portion of the developmental effort be
undertaken by Lucid under a subcontract, as discussed below. [We
recommend that a sole source contract be negotiated with Lucid, Inc.
because Richard Gabriel, who is a founder and President of Lucid, is the
co-inventor of Qlisp.]

For the implementation task, we plan to acquire one multiprocessor system
and make it accessible to all participants via communication links.
Toward this end, we have budgeted for a microwave link between Lucid's
offices and the Stanford campus ethernet, which will also provide linkage
to ARPAnet. For the follow-on application and testing task it may be
necessary to acquire an additional system.

We have carefully examined a number of possible system configurations from
a number of prospective suppliers, including BBN, Denelcor, Encore,
Sequent, Symbolics, and Synapse. It appears that several machines that
could meet our needs are available. We propose to choose the most
suitable system available at the time funding becomes available. The
budget has been formulated based on the Sequent Balance 8000, which is one
of the machines that appears suitable, but we are leaving the final
selection open for now.

Collaboration and connections with other projects

There are several other groups working on aspects of parallel symbolic
computation with whom collaboration will have mutual benefit. Two
particular projects are:

(HPP-AA) The advanced architectures group from the heuristic programming
project as Stanford (Feigenbaum, Nii)

(SPUR) The parallel Lisp on a RISC machine project at UC Berkeley

Some obvious benefits come from the opportunity to share ideas
on real parallel programming techiques and the problems to be solved.
In addition there are some specific benefits.

The advanced architecture project will benefit from having a parallel
Lisp running on real machine rather than using simulations. They are
working on parallel implementation of the blackboard model for expert
systems which will provide an additional substantial application with
emphasis on AI methods and asynchronous interactions. This will provide
input on additional primitives needed in Qlisp and programs for testing
implementation of these primitives. There is already some on-going
collaboration with regard to designing parallel control structures and
testing them in a simulation of Qlisp.

The SPUR project will get additional applications for testing their
primitives including benchmarks designed for Qlisp and for the Macsyma
application. There can be mutual input on parallel primitives at
software, operating system and hardware levels. In a later stages,
assuming good progress on the part of both projects, it will be reasonable
to implement Qlisp on the SPUR machine. Collaboration with the SPUR group
will be facilitated by our collaboration with Fateman on the Macsyma
application.

Parallel Algorithms for Algebraic Manipulation

[This part of the project will be done by Richard Fateman and his group at
U.C. Berkeley.]

We propose to design, implement, and test algorithms in Qlisp
for the purpose of
(i) validating the Qlisp primitives and compiler design,
(ii) demonstrating realistic applications where the high speed provided
by multi-processing can be put to good use.

Our areas of interest include algebraic manipulation programs (typified by
Macsyma) and other symbolic mathematical computations. These programs
have benefitted in the past by advances in computer hardware (large
address spaces, cheap memory, high speed), and should lead in the use of
non-numeric parallel processing. While past uses have been primarily in
applied mathematics and engineering, and occasionally in theorem proving,
number theory, and compiler theory, it appears that there is an increasing
interest in symbolic mathematics capabilities for computer-aided design
and AI applications.

Since important algorithms have already been refined over the past dozen
years or more in serial implementations, we have an opportunity to make
realistic judgments regarding the advantages of parallel programs.

While it is not possible to identify all opportunities for parallelism
at the outset, we can suggest the following directions:

1. Exploit obvious cases of traditional parallel algorithms, e.g. FFT for
multiplying polynomials. The FFT in symbolic manipulation is done in a
finite computation structure (not complex floating-point numbers), but is
otherwise similar to the usual FFT.

2. Use multiple processors to multiply two polynomials by divide and
conquer, or by farming out partial products. Combining partial products by
addition is tricky, and hash-coding by exponents (to coalesce
corresponding coefficients) may provide a neat application.

3. Examine multiple-homomorphism (mod Q) algorithms such as polynomial
GCD, trying to do several moduli at the same time, for example. The GCD
problem has been well studied, but GCD computation can nevertheless occupy
large amounts of time in certain common manipulations (e.g. addition of
rational functions.).

4. In factoring polynomials over the integers, several moduli generally
used in a first step (factoring polynomials over several finite fields).
This could clearly be done in parallel, although this is not usually the
expensive part of the algorithm. Combinatorial matching of factors of
different degrees is much more time-consuming; an extravagant number of
moduli can sometimes simplify the matching. Alternatively, the matching
process could be done in parallel.

5. Linear algebra algorithms: some classical calculations have been shown
to run relatively faster with symbolic entries, using methods that are
highly appropriate for parallel calculation, even though the same methods
are terrible for floating-point. The best known example is the
computation of matrix determinants for which expansion by minors is
believed superior to Gaussian elimination. Actually implementing this on
a multiprocessor should make good use of division of labor.

6. General simplification of expressions represented in trees: to simplify
f(a,b,c,...) one simplifies a,b,c,... to a', b', c', ...
and then simplifies f(a', b' , ...).
Two improvements are obvious: simplify the arguments in parallel;
sort the arguments by a parallel sort (e.g. if f is +, or some
other commutative operation).

7. Pattern matching drives some algorithms (e.g. indefinite integration).
Heuristic pattern matching with back-tracking may become more practical
with parallel processing, and should perhaps be revived as a more
fundamental control structure in some of the problem-solving programs.

8. Parallel garbage collection of cons cells or other (much larger) data
objects constructed by algebraic manipulation might be worth exploring.

9. We have experimented with frame-based objects with multiple
representations: we could compute simultaneously with different forms
(e.g.
polynomials:[expanded, recursive, factored],
curves:[parametric, point-set, constraints],
matrices:[dense, \break sparse, factored])

Resources needed:

We assume there will be an implementation effort at Stanford which
will produce a Qlisp simulation and an actual Qlisp implementation
on a parallel architecture machine.

The simulation would be available for use on hardware already in place
at UCB (including VAX, SUN, Symbolics, or Xerox), but the actual
parallel processor would be at Stanford. Substantial computing would
be required at UCB for program preparation, testing, communication,
etc.

Reference:

Gabriel, Richard and John McCarthy (1984):
``Queue-based Multi-processing Lisp''
in "Proceedings of the 1984 ACM Symposium on Lisp and Functional Programming",
August 1984.

APPENDIX A

[A contract to implement Qlisp will be negotiated on the basis of the
following proposal from Richard Gabriel of Lucid, Inc.]

Proposal to Implement Qlisp.

Introduction

The purpose of the work proposed here is to produce a Qlisp
which runs on commercially available multiprocessor hardware.
The implementation will be a native-code Qlisp---there will be
a compiler that produces code that the processors in a multiprocessor
execute directly. This is contrasted with a compiler that produces
an abstract machine language that an interpreter running on the
multiprocessor interprets.

This part of the proposal is in several sections. The first describes the
technical issues, the second describes Lucid's ability to perform the
work, and the last section is an accounting of the anticipated level of
work to accomplish the goals as well as a set of milestones.

Implementing Qlisp

Qlisp is a dialect of Lisp with extensions for multiprocessing.
The extensions require the implementation of locking primitives,
interprocessor interrupts, a simple queue-based scheduler for
the multiprocessor, process creation, process killing, and process
protection.

For each of these operations, the implementation may need to rely on
facilities provided by either the hardware or the operating system. Lucid
is prepared to do some operating system work in the form of modifications
to existing software to accomodate these needs, but Lucid shall not
be held in breech of contract if forces beyond its control prevent
such modifications by Lucid. Furthermore, if the operating system and
hardware prove to be inadequate for implementing Qlisp, and if there
is no recourse available from the hardware supplier, Lucid shall not
be held in breech of contract for failure to develop the needed software.

Shared Memory/Shared Address Space

Implementing Qlisp requires a multiprocessor in which all of the processes
can operate on a shared heap. This does not require that the machine has
a uniformly shared memory, but it does require a shared address space.
A multiprocesor with some local non-shared address space memory might
provide good performance if code is executed from that local memory.
However, in this case there must be a means to `page' code from the global
memory into the local memories as needed, or else each local memory must
be large enough to hold all of the program code.

The Global Queue

Qlisp requires that there be globally accessible queue of runnable
Qlisp processes, and that this queue be user-modifiable using
very strict functions. The user is able to place processes in the
queue using QLET and by invoking process closures created using
QLAMBDA. Also, using CATCH/QCATCH/THROW the user is able to remove
processes.

The original formulation of Qlisp required that the processors would
timeshare among processes so that every process that was actually runnable
would make some progress, though the progress might be minimal. On several
candidate machines this ability might be too costly (in terms of
efficiency) to provide. In this event Lucid will explore the possibility
of restricting the creation of new processes so that the number of
processes created will not exceed the number of processors available.

Function Calling

Qlisp requires a heavy use of closures. In order to minimize the cost of
creating and passing around closures, Qlisp will not use a stack for control.
Rather it will use what is called a `Big Bag of Frames' (BBOF). The idea is
that each function will manipulate a heap-allocated frame rather than a
stack allocated frame. This little block of storage, along with pointers
from each one to the parent frame and other closure frames, will make
closure implementation simple. Also, the process structures will simply be
a pair, one pointing to a frame and another to a code vector.

There will be a performance penalty for non-parallel Lisp code using this
scheme, but by pre-allocating a number of various sizes of frames, perhaps
using a buddy-block scheme, this penalty can be reduced. Some preliminary
experiments show that the function-calling performance degradation can
be as low as 15\%.

This scheme, by the way, is essentially the same one that is used by the
IBM PL1 language.

Process Structure

A process closure will be a frame, a pointer to a code vector, a saved
state, a queue of messages that have been sent to a process along with
possible return addresses for those messages, and a list of cleanup forms
to execute if the processes is killed. The cleanup forms are executed
while the processes are not killable, which guarantees that the cleanup
forms get executed.

Locking Primitives

Qlisp will need to implement the ability to exclude other processes
from using given resources. A simple spin lock based on test-and-set will
be sufficient for this, though test-and-add would be better. From this Qlisp
will provide a simple lock mechanism and perhaps a semaphore mechanism at
user level.

Interprocessor Interrupts

In order to implement CATCH/QCATCH/THROW it must be possible to examine
processes and to kill them. The general scheme is that there is a global
queue of processes that are, in principle, ready to run. A data structure is
built containing pointers to specific processes. These processes may be waiting
an available processor or else they are being executed. Certain actions by
other processes will require that these specified processes be interrupted
and killed. The processes will not be killed immediately if there is some
cleanup code specified for them. That is, Qlisp requires that the
programmer be able to execute a process in such a way that certain actions,
like closing files, be done before the process is terminated.

Killing processes outright can be accomplished by scanning through the
data structure of processes to kill, determining which processes are
running, and to remove the non-running ones from the runnable queue and
interrupting the processors running the killable processes.

To implement this requires that the hardware support processor-to-processor
interrupts and that the operating system allows such interrupts and
can provide for user code being run when an interrupt occurs.

Garbage Collection

Lucid will explore a variant of Halstead's garbage collection scheme, though
it is not anticipated that an incremental garbage collector will be
implemented. Most likely, a pure stop-and-copy garbage collector will
be implemented.

Lisp Implementation

Lucid will use a deep-binding Common Lisp as the basis for Qlisp. The
Qlisp primitives will be runtime extensions to the basic Common Lisp.
The compiler will only know a very little amount about the Qlisp
primitives. The most important change that will be made to the Common Lisp
is to use the BBOF calling scheme rather than the relatively simple
stack scheme used on other machines we support.

Lucid will provide whatever debugging aids as prove useful for its own
debugging. These aids will be relatively rudimentary, because the
development of sophisticated aids will depend on more extensive experience
with Qlisp.

Lucid

Lucid implements Common Lisps on `stock' hardware. This is accomplished
using a native-code compiler, which compiles Common Lisp to the native
instruction set of the target machines. Currently Lucid has implemented a
Common Lisp for MC68000-based computers running Unix
with virtual memory support. The Lisp system is
written to be portable, and there is little difficulty with porting it to
a NS32032-based computer running Unix with virtual memory support.

Lucid will use its portable Common Lisp as the basis for the Qlisp
implementation. Being a native-code Lisp, Qlisp will be a fairly
efficient implementation.

The work will take three years to complete and will be staged in such a
way that there will be a prototype Qlisp available approximately one year
after the start of work. During the first six months Lucid will port its
basic Common Lisp to the target computer; included in this will be the
change from a stack-based function-calling regime to the frame-based
regime. During the second six months Lucid will do an initial
implementation of the bulk of the initial Qlisp system. This
implementation will only spawn a number of processes equal to the number
of processes. No garbage collector will be written. UNWIND-PROTECT will
also be omitted, because that feature requires the operating system to
support user-code running `uninterruptably' after an earlier interrupt.
The initial system will also not include much in the way of debugging aid
for multiprocessing, though the Lisp itself will be well-equipped in this
area.

The point of the initial implementation is to allow the Lucid Qlisp staff
and the Stanford project members
to begin using and critiquing the implementation. Of special interest
will be the initial benchmarking of Qlisp to determine performance
bottlenecks, so that improvements to the design and implementation
can be made.

The second year will be devoted to advancing the implementation to the
point where it represents a complete Qlisp. Full spawining capabilities,
full UNWIND-PROTECT, and those improvements to the language and the
implementation that are suggested by the initial user community and that
appear most important will be done. Lucid anticipates that this phase of
the work will require some amount of operating system work, possibly with
the co-operation of the hardware manufacturer's operating system or
software group.

The third year will concentrate on tuning the implementation and working
closely with the Stanford Qlisp project's technical staff to remove
performance bottlenecks, to improve debugging aids, and to improve the
definition of Qlisp.

At the end of the project the following will have been delivered:

1. A working Common Lisp system, provided as a single copy on magnetic tape,
in the form of object code executable on a uniprocessor version of the
multiprocessor.

2. A working Qlisp in the form of extensions to Common Lisp. This shall
be a fully functioning Qlisp multiprocessor system. The source code for
Qlisp aside from that covered in number 1 will be available for Stanford
use and modification. The object code for the Qlisp implementation will be
placed in the public domain, especially for use by other DARPA
contractors.

3. A set of working papers and other documents describing the implementation
of Qlisp will be written and published at least as part of the Stanford
report on the project and, it is hoped, in journals or presented at conferences.

In summary, Lucid considers the sources for the portable Common Lisp,
which are sold as the Lucid Portable Common Lisp Development Environment
and as the Lucid Portable Common Lisp Application Environment as
proprietary. Lucid considers all deliverables of the Qlisp project that
are additions to the source code kernel for these Portable Common Lisp
products and that implement Qlisp as public domain. Lucid will retain the
right to use code developed during the project as commercial products.

Lucid assurances to Stanford

Lucid acknowledges that the participation of Dr. Richard Gabriel is
essential to the implementation of Qlisp. Lucid agees to notify the
Principal Investigator of the Qlisp project if Dr.~Gabriel is unable to
fulfill the minimum work level specified in the budget for a continuous
period of 60 days, such notification to be made within 5 working days of
this occurrence. Lucid shall have 60 days from the date of notification
to the Principal Investigator of Dr.~Gabriel's inability to continue on
the project to notify the Principal Investigator of a replacement to
Dr.~Gabriel. If the Principal Investigator approves the replacement,
Lucid shall have an additional 60 days (120 days cumulative) in which to
make Dr.~Gabriel's replacement available for Qlisp participation.

If Lucid is unable to meet these deadlines or the Principal Investigator
does not approve of the replacement for Dr. Gabriel, Stanford University
shall have as its sole remedy the right to terminate this contract, but
shall retain the right to use the Qlisp multiprocessor system to the
extent that it has been developed, including the Common Lisp object code,
Neither Stanford University nor Lucid shall have any obligation to the
other party after termination. In the event of termination, Lucid shall
retain rights to its Licensed Software.

The Qlisp development and support staff at Stanford will have the right
to unlimited use of all Lucid Portable Common Lisp object code for work
in association with the Qlisp project.

Lucid agrees to keep an escrow account which contains all the source
code and documentation, including all updates and bug fixes to the
Lucid Portable Common Lisp products. In the event of a complete
termination of Lucid as a business, the Qlisp project will have the
non-exclusive rights to use the escrow contents for the sole purpose
of continuing the Qlisp project.

At Stanford's option, Lucid also agrees to maintain the software developed
under this contract for up to an additional three years beyond normal
termination of this contract. The fees for this work would be the same as
for the third year of this proposal, adjusted for inflation.

In the event that Lucid is unable to perform due to its termination
as a business and Stanford is unable to gain access to the Lucid escrow
account, Stanford Qlisp research personnel shall have access to the
Lucid source code and docuumentation at Lucid's site.

APPENDIX D -- Budget for eighteen months beginning 1 December 1985.

Stanford University proposal to DARPA
for
Qlisp on parallel processors

Budget for period 1 2
duration 1 year 6 months
beginning 12-1-85 12-1-86
ending 11-30-86 5-31-87
Personnel
Prof. John McCarthy, Principal Investigator 21,058 6,650
(15% acad. yr., 50% summer)

Lester Earnest, Senior Res. Assoc. (100%) 67,500 33,750

Carolyn Talcott, Research Associate (100%) 43,000 21,500

-----, Research Associate (100%) 41,000 20,500

-----, Computer Systems Analyst (100%) 40,000 20,000

-----, Computer Technician (25%) 8,000 4,000

Ross Casley, Student Research Assistant 12,600 5,040
(50% acad. yr., 100% summer)
Ian Mason, Student Research Assistant 12,600 5,040
(50% acad. yr., 100% summer)
-----, Student Research Assistant 5,040
(50% acad. yr., 100% summer)
-----, Student Research Assistant 5,040
(50% acad. yr., 100% summer)
-----, Secretary (50% time) 10,440 5,220
------- -------
Salary subtotals 256,198 131,780

Allowance for salary increases (9%/yr) 0 11,860
------- -------
Salary totals 256,198 143,640

Staff benefits (25.4% initially, 65,202 36,772
25.6% beg. 9/1/86)

Consultants (10 days/yr. @ $500) 5,000 2,500

Capital equipment
Multiprocessor computer system
(e.g. Sequent Balance 8000 system) 307,580
Ethernet workstation cluster (8 term.) 24,000
Ethernet page printer 11,937
Microwave link 30,000
Additional workstations & peripherals 12,000

U.C. Berkeley subcontract 182,000 102,481

Lucid subcontract 518,000 204,600

Indirect costs (69% of direct costs 340,873 179,556
initially, 73% beginning 9/1/86,
excluding all capital equipment and
subcontract amounts over $25,000) ------- -------

Total by period 1,901,264 744,604
------- -------
Project cumulative total 1,901,264 2,645,868

U.C. Berkeley Budget

18 months beginning 12/1/85

A. Salaries & Wages 1) Period from 12-1-85 12-1-86
to 11-30-86 5-31-87

No. Position (Time) Monthly Total

1 Professor (1 Mo. summer) 5356 $5,356 **
Student Post Grad Res.
2 (1 Mo. @ 80% 1995 3,192 +
2 Mo. @ 80% 2109 6,749 +
4 Mo. @ 50% 2109 8,436 ++
5 Mo. @ 50%) 2174 10,870 ++
3 (6 Mo. @ 50%) 2337 ++ 21,033
1 Programmer 3 (1 Mo. @ 50% 2504 1,252 *
11 Mo. @ 50%) 2647 14,559 *
(6 Mo. @ 50%) 2948 * 8,844
1 Admin. Assist. I
(1 Mo. @ 25% 1612 403 *
11 Mo. @ 25%) 1704 4,686 *
(6 Mo. @ 25%) 1815 * 2,722
Var. Clerical (12 Mo.) 300 3,600 *
(6 Mo.) 340 2,040

Total Salaries & Wages $59,103 $34,639

1) All Salaries and Wages are based on current published University rates,
and include an estimated 5.7% range adjustment effective July 1,1985 then
a 7.5% for academic titles and a 6.5% for staff title on each July 1
thereafter. Individual merit increases are included when applicable.
Academic titles include an additional 3.1% range adjustment effective
1/1/86, then a 7.5% for academic titles and a 6.5% for staff titles on
each July 1 thereafter.

B. Employee Benefits

28.25% salaries marked * $6,921 $3,844
19.78% salaries marked ** 1,059 0
1.43% salaries marked + 142 0
.92% salaries marked ++ 178 194

Total Employee Benefits $8,300 $4,038

C. Permanent Equipment

Qty Description Cost

1 Fujitsu Disk Drive 10,000
1 Fujitsu Disk Drive 10,000

Total Equipment $10,000 $10,000

D. Travel

Domestic: as follows, to participate in technical meetings related to
proposed research; Three round trips (Principal Investigator and two
studens to attend technical conference related to proposed research (e.g.
SYMSAC Conference 1986). $800 air fare; four days per diem at $400;
registration fee $100; misc. and ground transportation - $50.

Total Travel $4,050 $2,025

E. Supplies & Expense

Sun Microsystems, Inc. 5,000 2,025
In-house support groups 37,962 18,981
based on 1,850 hours @ $20.52/hour.
Expendable research supplies 3,530 1,765
Mailing, Telephone, Xerox, Office 1,500 750

Total Supplies & Expenses $47,992 $23,521

F. Total Direct Costs $129,445 $74,223

G. Indirect Costs
44% of Total Direct Costs excluding $52,555 $28,258
permanent equipment.

TOTAL COST OF RESEARCH PROGRAM $182,000 $102,481
Lucid
Project Cost Estimate
($000's)
Half-
Year 1 Year 2

Direct Labor (Sch. A) 109.2 56.7

Salary Related Expense @19.8% 21.6 11.2
-----------------
Salary Expense 130.8 67.9

Overhead @148% 193.6 100.5

Other Direct Project Costs
(Sch. B) 126.0 9.5
-----------------
450.4 177.9

Fee @15% 67.6 26.7
-----------------
Total Project Cost 518.0 204.6

Notes:
1. Project cost assumes 1 Sequent machine provided to Lucid at no additional
cost located at Lucid facilities for duration of project.

2. Salary Related Expense and overhead are provisional rates based on FY86
(year end June 30) business plan projections.

3. Direct Labor rates escalated at 10% per year.

Schedule A
Direct Labor
($000's)
Half-
Year 1 Year 2

Principal Investigator
man-months 3 1
rate per month 6.0 6.6
total dollars 18.0 6.6

Senior Scientist
man-months 12 6
rate per month 5.0 5.5
total dollars 60.0 33.0

Scientist
man-months 6 3
rate per month 4.2 4.6
total dollars 25.2 13.8

Technician
man-months 2 1
rate per month 3.0 3.3
total dollars 6.0 3.3

Total Man-Months 23 11

Total Dollars 109.2 56.7

Schedule B
Other Direct Project Costs
($000's)

Half-
Year 1 Year 2

Computer Equipment & Supplies
Symbolics 3670 108
Supplies @ 3K/yr 3 1.5
Stanford Communication 2 1

Travel & Subsistence
Air
2 trips to Washington, D.C. @1.5 ea.
1 trip to National Conference @1.5
4 trips to East Coast, technical workshop @1.5 ea.

Local travel @.5/yr 11 6
escalate @10%/yr

Printing and Reproduction @2K/yr 2 1
---------------
Total 126 9.5
APPENDIX D -- Budget for eighteen months beginning 1 December 1985.

Stanford University proposal to DARPA
for
Qlisp on parallel processors

[Recommended related work at University of California at Berkeley is not
included in this budget.]

Budget for period 1 2
duration 1 year 6 months
beginning 12-1-85 12-1-86
ending 11-30-86 5-31-87
Personnel
Prof. John McCarthy, Principal Investigator 21,058 6,650
(15% acad. yr., 50% summer)

Lester Earnest, Senior Res. Assoc. (100%) 67,500 33,750

Carolyn Talcott, Research Associate (100%) 43,000 21,500

-----, Research Associate (100%) 41,000 20,500

-----, Computer Systems Analyst (100%) 40,000 20,000

-----, Computer Technician (25%) 8,000 4,000

Allowance for salary increases (9%/yr) 0 11,860
------- -------
Salary totals 256,198 143,640

Staff benefits (25.4% initially, 65,202 36,772
25.6% beg. 9/1/86)

Consultants (10 days/yr. @ $500) 5,000 2,500

Travel (8 East Coast trips/yr. @ $1000, 15,000 7,600
14 Western trips @ $500, adjusted for
inflation)
Computer maintenance 73,819 18,455
(based on Sequent Computer)
Computer time costs (based on 1984 usage 36,000 24,000
of SAIL computer by principals)
Other direct costs 22,600 13,000
------- -------
Subtotal 473,819 245,967
Capital equipment
Multiprocessor computer system
(e.g. Sequent Balance 8000 system) 307,580
Ethernet workstation cluster (8 term.) 24,000
Ethernet page printer 11,937
Microwave link 30,000
Additional workstations & peripherals 12,000

Lucid subcontract 518,000 204,600

Indirect costs (69% of direct costs 349,173 179,556
initially, 73% beginning 9/1/86,
excluding all capital equipment and
subcontract amounts over $25,000) ------- -------

Total by period 1,714,509 642,123
------- -------
Project cumulative total 1,714,509 2,356,632

Lucid
Project Cost Estimate
($000's)
Half-
Year 1 Year 2

Direct Labor (Sch. A) 109.2 56.7

Salary Related Expense @19.8% 21.6 11.2
-----------------
Salary Expense 130.8 67.9

Overhead @148% 193.6 100.5

Other Direct Project Costs
(Sch. B) 126.0 9.5
-----------------
450.4 177.9

Fee @15% 67.6 26.7
-----------------
Total Project Cost 518.0 204.6

Notes:
1. Project cost assumes 1 Sequent machine provided to Lucid at no additional
cost located at Lucid facilities for duration of project.

2. Salary Related Expense and overhead are provisional rates based on FY86
(year end June 30) business plan projections.

3. Direct Labor rates escalated at 10% per year.

Schedule A
Direct Labor
($000's)
Half-
Year 1 Year 2

Principal Investigator
man-months 3 1
rate per month 6.0 6.6
total dollars 18.0 6.6

Senior Scientist
man-months 12 6
rate per month 5.0 5.5
total dollars 60.0 33.0

Scientist
man-months 6 3
rate per month 4.2 4.6
total dollars 25.2 13.8

Technician
man-months 2 1
rate per month 3.0 3.3
total dollars 6.0 3.3

Total Man-Months 23 11

Total Dollars 109.2 56.7
Qlisp revised budget
Here is a revised budget covering the last half of FY86 and all of FY87.
As requested, it omits the parallel computer but includes other required
equipment and is squeezed down on several items. As you can see, the
bottom line is $1,869,388 for the 18 month period.

I will contact Ike Nasssi as you suggest. Given that whatever computer we
buy now will be a shared-use machine, that Sequent has been delivering
parallel systems longer than the competition, that their software seems to
work and that they enjoy a reputation for meeting commitments, there will
have to be strong reasons for choosing something other than the Sequent
machine. I would be interested in whatever insights you may have on this
issue.

Les Earnest

-------------------------------

APPENDIX D -- Budget for eighteen months beginning 1 April 1986.

Stanford University proposal to DARPA
for
Qlisp on parallel processors

[Funds fo the required parallel computer are NOT included.]

Personnel
Prof. John McCarthy, Principal Investigator 36,000
(15% acad. yr., 50% summer)

Lester Earnest, Senior Res. Assoc. (50%) 50,625

Carolyn Talcott, Research Associate (100%) 64,500

-----, Research Associate (100%) 61,500

-----, Computer Systems Analyst (100%) 60,000

-----, Computer Technician (25%) 12,000

Ross Casley, Student Research Assistant 20,160
(50% acad. yr., 100% summer)
Ian Mason, Student Research Assistant 20,160
(50% acad. yr., 100% summer)
-----, Student Research Assistant 7,560
(beg. 4/1/87; 50% acad. yr.,
100% summer)
-----, Student Research Assistant 7,560
(beg. 4/1/87; 50% acad. yr.,
100% summer)
-----, Secretary (50% time) 15,660
-------
Salary subtotals 340,065

Allowance for salary increases 22,104
(9% beginning 9/1/86)
-------
Salary totals 362,169

Staff benefits (25.6%) 92,715

Consultants (10 days/yr. @ $500) 7,500

Travel (8 East Coast trips/yr. @ $1000, 22,500
14 Western trips/yr. @ $500)
Computer maintenance 45,000

Computer time costs 50,000

Other direct costs 36,100
-------
Subtotal 615,984

Capital equipment
Ethernet workstation cluster (8 term.) 24,000
Ethernet page printer 11,937
Microwave link 30,000
Interfacing equipment & peripherals 12,000
-------
Subtotal 77,937

Lucid subcontract 722,600

Indirect costs (69% of direct costs 460,869
initially, 73% beginning 9/1/86,
excluding all capital equipment and
subcontract amounts over $25,000) -------

Total $1,877,388

Qlisp Task Description
[Here is a proposed task description for the Qlisp project, which is to
be added to Contract N00039-84-C-0211, including a revised budget keyed
to a 1 June 1986 start. I invite comments on any problems that you might
see. Given that you already have a full proposal for this project, should
I put just the budget through the Stanford bureaucracy or should the text
of the task description also follow that route? -Les]

An extension of Common Lisp for parallel processing, called Qlisp, is to
be developed using queue-based multi-processing, as described in Gabriel &
McCarthy, "Queue-based Multiprocessor Lisp" in Proceedings of the 1984 ACM
Symposium on Lisp and Functional Programming, August 1984. It will have
the following features.

o Each processor can address the whole of memory, and a processor may
execute programs anywhere in memory on data located anywhere in memory.

o The programmer indicates when parallelism is possible by using parallel
constructions in the source language, which is an extension of Lisp.

o When a processor completes a task it goes to the queue for its next task.

This task covers the first phase of an expected three year program,
involving a collaboration between Stanford University, and Lucid, Inc.
This task of 18 months duration will produce a functioning Qlisp system,
documentation and debugging tools at a cost of $1,943,464. Assuming this
project starts on 1 June 1986, specific milestones are as follows.

1 Dec. 1986: Have a monoprocessor version of a subset of Common Lisp suitable
for parallel computation working on the chosen parallel computer.
Preliminary specification of Qlisp extensions to Common Lisp completed.

1 June 1987: Preliminary version of Qlisp working, with preliminary
documentation. Specification of test problems to be run will be complete.

30 Nov. 1987: Improved version of Qlisp completed together with documentation.
Test results of sample problems run on the parallel computer documented.

This is planned as a step toward the longer range goal of demonstrating
symbolic computation in a parallel computing system.

APPENDIX D -- Budget for 18 months from 1 June 1986 through 30 Nov. 1987

Stanford University proposal to DARPA
for
Qlisp on parallel processors

[Funds for the required parallel computer are NOT included.]

Personnel
Prof. John McCarthy, Principal Investigator 35,467
(15% acad. yr., 50% summer)

Lester Earnest, Senior Res. Assoc. (50%) 50,625

Carolyn Talcott, Research Associate (100%) 64,500

-----, Research Associate (100%) 61,500

-----, Computer Systems Analyst (100%) 60,000

-----, Computer Technician (25%) 12,000

Ian Mason, Student Research Assistant 20,160
(50% acad. yr., 100% summer)
-----, Student Research Assistant 20,160
(50% acad. yr., 100% summer)
-----, Student Research Assistant 7,560
(beg. 6/1/87; 50% acad. yr.,
100% summer)
-----, Student Research Assistant 7,560
(beg. 6/1/87; 50% acad. yr.,
100% summer)
-----, Secretary (50% time) 15,660
-------
Salary subtotals 355,192

Allowance for salary increases 28,415
(8% beginning 9/1/86,
16% beginning 9/1/87)
-------
Salary totals 383,607

Staff benefits (25.4% till 9/1/86, 98,459
25.6% till 9/1/87, then 26.2%)

Consultants (10 days/yr. @ $500) 7,500

Travel (8 East Coast trips/yr. @ $1000, 22,500
14 Western trips/yr. @ $500)
Computer maintenance 64,548

Computer time costs 40,000

Other direct costs 36,100
-------
Subtotal 652,714

Capital equipment
Ethernet workstation cluster (8 term.) 24,000
Ethernet page printer 11,937
Microwave link 30,000
Interfacing equipment & peripherals 12,000
-------
Subtotal 77,937

Lucid subcontract 722,600

Indirect costs (69% of direct costs 490,213
initially, 73% beginning 9/1/86,
excluding all capital equipment and
subcontract amounts over $25,000) -------

Total $1,943,464

Lucid
Project Cost Estimate
($000's)
Half-
Year 1 Year 2

Direct Labor (Sch. A) 109.2 56.7

Salary Related Expense @19.8% 21.6 11.2
-----------------
Salary Expense 130.8 67.9

Overhead @148% 193.6 100.5

Other Direct Project Costs
(Sch. B) 126.0 9.5
-----------------
450.4 177.9

Fee @15% 67.6 26.7
-----------------
Total Project Cost 518.0 204.6

Notes:
1. Project cost assumes access to the selected parallel computer at Lucid
facilities provided to Lucid at no additional cost for duration of project.

2. Salary Related Expense and overhead are provisional rates based on FY86
(year end June 30) business plan projections.

3. Direct Labor rates escalated at 10% per year.

Schedule A
Direct Labor
($000's)
Half-
Year 1 Year 2

Principal Investigator
man-months 3 1
rate per month 6.0 6.6
total dollars 18.0 6.6

Senior Scientist
man-months 12 6
rate per month 5.0 5.5
total dollars 60.0 33.0

Scientist
man-months 6 3
rate per month 4.2 4.6
total dollars 25.2 13.8

Technician
man-months 2 1
rate per month 3.0 3.3
total dollars 6.0 3.3

Total Man-Months 23 11

Total Dollars 109.2 56.7

Schedule B
Other Direct Project Costs
($000's)

Half-
Year 1 Year 2

Computer Equipment & Supplies
Symbolics 3670 108
Supplies @ 3K/yr 3 1.5
Stanford Communication 2 1

Travel & Subsistence
Air
2 trips to Washington, D.C. @1.5 ea.
1 trip to National Conference @1.5
4 trips to East Coast, technical workshop @1.5 ea.

Local travel @.5/yr 11 6
escalate @10%/yr

Printing and Reproduction @2K/yr 2 1
---------------
Total 126 9.5
Qlisp Task

John McCarthy, Professor of Computer Science
Principal Investigator
BACKGROUND

This research is for the implememntation and demonstration
of applications of an extension of Lisp for parallel processing
called Qlisp. Qlisp allows the programmer to specify tasks that
may be performed in parallel by creating queues of tasks. This
project involves developing Qlisp for a parallel processor,
developing test applications for it, and testing the performance
of the applications on substantial symbolic computation tasks.

This project's approach is queue-based multi-processing. It
has the following features:

Each processor can address the whole of memory, and a
processor may execute programs anywhere in memory on data located
anywhere in memory.

The programmer indicates when parallelism is possible by
using parallel constructions in the source language, which is an
extension of Lisp.

When a program comes to a statement allowing parallelism and
decides (according to the computed value of an allow-parallelism
parameter in the statement) that parallelism is to be invoked, it
adds a collection of tasks to a queue and starts on the first.

When a processor completes a task it goes to the queue for
its next task. It may execute some queue management code to
decide what to do next.

Basing parallelism on run-time queues means that a program
isn't written or compiled for any specific number of processors.
The number available can even change during the course of a
computation. Tasks need not be of similar length, because a
processor finishing a short task merely takes another queue.

It is necessary to follow through on the development and
implementation of Qlisp by trying it out on substantial
applications. These trials will most likely lead to improvements
in Qlisp and in the parallel processing hardware. They may also
determine whether it is possible to relax the requirement that
all memory be equally accessible to all processors, since the
hardware people find this expensive to implement.

There are two kinds of problems to which parallelism can be
applied. In one case the goal is to make what you already have
run faster. This improves interaction with the computer and
allows larger problems to be addressed. In the second case,
speed is of the esssence. Part of the algorithm is devoted to
insuring speed and some sort of real time behavior. For example,
a process may want to time out or use some default value if a
subprocess does not reply within a given time limit. Qlisp
primitives directly address problems of the first sort.
Additional primitives may be needed for the real time
applications.

TOOLS FOR PARALLEL SYMBOLIC PROGRAMMING

This work involves an entirely new style of programming and
will require the development of new methods and tools to support
the programming activity. This development will be carried out
in parallel with and in support of the chosen application.

Algorithm Design

Part of the development of parallel Lisp involves
discovering what primitives are needed to carry out various
tasks. This involves classifying problems as to the sort of
parallelism required and the design of control structures
appropriate for the various classifications. Two well known
classifications are AND versus OR parallelism and asynchronous
tasks with occasional interactions versus synchronous tasks
operating on a shared data structure. Somewhat newer ideas
include pipelines and other geometric structures that make it
easy to visualize the interactions among a set of processes. In
some cases successful use of parallelism will require design of
data structures with information making them suited to parallel
processing.

Methods For Debugging

Traditional Lisp debugging methods such as stepping and
tracing are not going to be adequate for debugging Qlisp
programs. Programmers will need to learn where to look for bugs
and to devise methods for identifying meaningful checkpoints.
This effort shall include the building of tools for monitoring
the progress of a set of processes working on a problem. It
shall also include work on informal methods of specification and
reasoning about Qlisp programs as aids to the process of program
development and testing.

Benchmarks and Measures of Success

Benchmarks for testing parallel Lisp and for comparing the
relative efficiency of parallel and sequential algorithms shall
be designed. Also tools for measuring factors such as degree of
parallelism achieved, queue management overhead, and memory
contention shall be developed. Some measuring tools have already
been developed by Gabriel in a sophisticated system for
simulating execution of Qlisp programs. This system was used in
initial experiments testing Qlisp primitives.

MILESTONES

7 Months After Initiation of Task (MAIT) - Have a monoprocessor
version of a subset of Common Lisp suitable for parallel
computation working on a chosen parallel computer.
Preliminary specification of Qlisp extensions to Common Lisp
completed.

12 MAIT - Preliminary version of Qlisp working, with preliminary
documentation. Specification of test problems to be run shall be
completed.

18 MAIT - Improved version of Qlisp completed together with
documentation. Test results of sample problems run on the
parallel computer documented.

DELIVERABLES

12 MAIT - Copy of preliminary documentation.

Report detailing the specification of the test problems to
be run.

18 MAIT - Copy of documentation on the improved Qlisp.

Report detailing test results of sample problems.

19 MAIT - Final report on task, including progress, lessons
learned, and future research to be considered.

In addition to the above stated milestones and deliverables,
quarterly progress reports shall be submitted in accordance with
DARPA/SPAWAR 613 reporting instructions.

BUDGET (18 months)

No capital equipment will be purchased without prior approval of DARPA.

Personnel
Prof. John McCarthy, Principal Investigator 35,467
(15% acad. yr., 50% summer)

Lester Earnest, Senior Res. Assoc. (50%) 50,625

Carolyn Talcott, Research Associate (100%) 64,500

-----, Research Associate (100%) 61,500

-----, Computer Systems Analyst (100%) 60,000

-----, Computer Technician (25%) 12,000

Allowance for salary increases 28,415
(8% beginning 9/1/86,
16% beginning 9/1/87)
-------
Salary totals 383,607

Staff benefits (25.4% till 9/1/86, 97,053
25.1% till 9/1/87, then 26.0%)

Consultants (10 days/yr. @ $500) 7,500

Travel (8 East Coast trips/yr. @ $1000, 22,500
14 Western trips/yr. @ $500)
Computer maintenance 64,548

Computer time costs 40,000

Other direct costs 36,100
-------
Subtotal 651,308

Capital equipment
4 Sun 3/50M-4 Workstations 22,120
2 Fujitsu "Eagle" disk drives 15,600
1 Alliant K002 cabinet 7,500
Interfacing equipment & peripherals 4,000
-------
Subtotal 49,220

Lucid subcontract 722,600

Indirect costs (69% of direct costs 489,196
initially, 73% beginning 9/1/86,
excluding all capital equipment and
subcontract amounts over $25,000) -------

Total $1,912,324

Lucid
Project Cost Estimate
($000's)
Half-
Year 1 Year 2

Direct Labor (Sch. A) 109.2 56.7

Salary Related Expense @19.8% 21.6 11.2
-----------------
Salary Expense 130.8 67.9

Overhead @148% 193.6 100.5

Other Direct Project Costs
(Sch. B) 126.0 9.5
-----------------
450.4 177.9

Fee @15% 67.6 26.7
-----------------
Total Project Cost 518.0 204.6

Notes:
1. Project cost assumes access to Alliant machine provided to Lucid
at no additional cost through a communication link to Lucid facilities
with a bidirectional transfer rate of at least 56 K bits/s. for duration
of project.

2. Salary Related Expense and overhead are provisional rates
based on FY86 (year end June 30) business plan projections.

3. Direct Labor rates escalated at 10% per year.

Schedule A
Direct Labor
($000's)
Half-
Year 1 Year 2

Principal Investigator
man-months 3 1
rate per month 6.0 6.6
total dollars 18.0 6.6

Senior Scientist
man-months 12 6
rate per month 5.0 5.5
total dollars 60.0 33.0

Scientist
man-months 6 3
rate per month 4.2 4.6
total dollars 25.2 13.8

Technician
man-months 2 1
rate per month 3.0 3.3
total dollars 6.0 3.3

Total Man-Months 23 11

Total Dollars 109.2 56.7

Schedule B
Other Direct Project Costs
($000's)

Half-
Year 1 Year 2

Computer Equipment & Supplies
Symbolics 3670 108
Supplies @ 3K/yr 3 1.5
Stanford Communication 2 1

Travel & Subsistence
Air
2 trips to Washington, D.C. @1.5 ea.
1 trip to National Conference @1.5
4 trips to East Coast, technical workshop @1.5 ea.

Local travel @.5/yr 11 6
escalate @10%/yr

Printing and Reproduction @2K/yr 2 1
---------------
Total 126 9.5